//David Andersen
// Based on BSP Dungeon Algorithm from RogueBasin - http://roguebasin.roguelikedevelopment.org/index.php/Basic_BSP_Dungeon_generation

using UnityEngine;
using System.Collections;

public class BSPNode {
	
	public int nodeIndex;
	public float left;
	public float top;
	public float width;
	public float height;
	public BSPNode leftChild;
	public BSPNode rightChild;
	public BSPNode parent;
	public Rect splitLine;
	public Rect room;
	public Rect corridor;
	
	public BSPNode (float left, float top, float width, float height, int nodeIndex)
	{
		this.left = left;
		this.top = top;
		this.width = width;
		this.height = height;
		this.nodeIndex = nodeIndex;
	}
	
	public float GetLeft()
	{
		return left;
	}
	
	public float GetTop()
	{
		return top;
	}
			
	public float GetWidth()
	{
		return width;
	}
	
	public float GetHeight()
	{
		return height;
	}
	
	public void SetParent(BSPNode parent)
	{
		this.parent = parent;
	}
	
	public void Split(float splitRatio,float splitRange)
	{
		if(leftChild == null)
		{
			float direction = Random.Range(0.0F,1.0F);
			if(direction <= 0.5F)
			{
				if(height < width * splitRatio)
				{
					SplitVertical(splitRange);
				}
				else
				{
					SplitHorizontal(splitRange);
				}
			}
			else
			{
				if(width < height * splitRatio)
				{
					SplitHorizontal(splitRange);
				}
				else
				{
					SplitVertical(splitRange);
				}
			}
		}
		else
		{
			leftChild.Split(splitRatio,splitRange);
			rightChild.Split(splitRatio,splitRange);
		}
	}
	
	public void SplitHorizontal(float splitRange)
	{
		float split = height * Random.Range(0.5F - (splitRange * 0.5F),0.5F + (splitRange * 0.5F));
		leftChild = new BSPNode(left, top, width, split,nodeIndex * 2);
		leftChild.SetParent(this);
		rightChild = new BSPNode(left, top + split, width, height - split,(nodeIndex * 2) + 1);
		rightChild.SetParent(this);
		splitLine = new Rect(left,(top + split) - 1,width,2);
	}
	
	public void SplitVertical(float splitRange)
	{
		float split = width * Random.Range(0.5F - (splitRange * 0.5F),0.5F + (splitRange * 0.5F));
		leftChild = new BSPNode(left, top, split, height,nodeIndex * 2);
		leftChild.SetParent(this);
		rightChild = new BSPNode(left + split, top, width - split, height,(nodeIndex * 2) + 1);
		rightChild.SetParent(this);
		splitLine = new Rect((left + split) - 1,top,2,height);
	}
	
	public void TraverseSplit(Rect[] splits)
	{		
		if(leftChild != null)
		{		
			splits[nodeIndex - 1] = splitLine;
			leftChild.TraverseSplit(splits);
			rightChild.TraverseSplit(splits);
		}		
	}
	
	public void GenerateRoom()
	{
		if(leftChild == null)
		{
			float roomLeft, roomTop, roomWidth, roomHeight;
			roomLeft = left + (width * Random.Range(0.1F,0.4F));
			roomTop = top + (height * Random.Range(0.1F,0.4F));
			roomWidth = width * Random.Range(0.4F,0.8F);
			roomHeight = height * Random.Range(0.4F,0.8F);
			if((roomLeft + roomWidth) >= (left + width))
			{
				roomLeft = (left + width) - (width * 0.1F) - roomWidth;
			}
			if((roomTop + roomHeight) >= (top + height))
			{
				roomTop = (top + height) - (height * 0.1F) - roomHeight;
			}
			room = new Rect(roomLeft, roomTop, roomWidth, roomHeight);
		}
		else
		{
			leftChild.GenerateRoom();
			rightChild.GenerateRoom();
		}
	}
	
	public void TraverseRooms(Rect[] rooms, int roomTotal)
	{
		if(leftChild == null)
		{
			rooms[nodeIndex - roomTotal] = room;
		}
		else
		{
			leftChild.TraverseRooms(rooms, roomTotal);
			rightChild.TraverseRooms(rooms, roomTotal);
		}
	}
	
	public void GenerateCorridors(Rect[] rooms,int roomTotal)
	{
		float splitPoint = 0;
//		float splitFinal = 0;
		float distance1 = 5000;
		float distance2 = 5000;
//		float corridorLength = 5000;
		int room1 = 0;
		
		if(leftChild != null)
		{
			if(splitLine.width > splitLine.height)
			{
				for(int j = 0; j < 50 || distance1 == 5000 || distance2 == 5000; j++)
				{
					distance1 = 5000;
					distance2 = 5000;
					float splitPointTemp = Random.Range(splitLine.x,splitLine.x + splitLine.width);
					splitPoint = splitPointTemp;
					
					for(int i = 0; i < roomTotal; i++)
					{
						if(rooms[i].x < splitPoint && rooms[i].x + rooms[i].width > splitPoint)
						{
							if(rooms[i].y < splitLine.y + 1)
							{
								float distanceTemp = (splitLine.y + 1) - (rooms[i].y + rooms[i].height);
								if(distanceTemp <= distance1)
								{
									distance1 = distanceTemp;
									room1 = i;
								}
							}
							else
							{
								float distanceTemp = rooms[i].y - (splitLine.y + 1);
								if(distanceTemp <= distance2)
								{
									distance2 = distanceTemp;
								}
							}
//							float corridorLengthTemp = distance1 + distance2;
//							if(corridorLengthTemp <= corridorLength)
//							{
//								corridorLength = corridorLengthTemp;
//								splitFinal = splitPoint;
//								room1 = i;
//							}
						}
					}					
				}
				if(distance1 == 5000 || distance2 == 5000)
				{
					corridor = new Rect(0,0,10,10);
				}
				else
				{
					corridor = new Rect(splitPoint - 2,rooms[room1].y + rooms[room1].height,4,distance1 + distance2);
				}
			}
			else
			{
				for(int j = 0; j < 50 || distance1 == 5000 || distance2 == 5000; j++)
				{
					distance1 = 5000;
					distance2 = 5000;
					float splitPointTemp = Random.Range(splitLine.y,splitLine.y + splitLine.height);
					splitPoint = splitPointTemp;
					
					for(int i = 0; i < roomTotal; i++)
					{
						if(rooms[i].y < splitPoint && rooms[i].y + rooms[i].height > splitPoint)
						{
							if(rooms[i].x < splitLine.x + 1)
							{
								float distanceTemp = (splitLine.x + 1) - (rooms[i].x + rooms[i].width);
								if(distanceTemp <= distance1)
								{
									distance1 = distanceTemp;
									room1 = i;
								}
							}
							else
							{
								float distanceTemp = rooms[i].x - splitLine.x + 1;
								if(distanceTemp <= distance2)
								{
									distance2 = distanceTemp;
								}
							}
//							float corridorLengthTemp = distance1 + distance2;
//							if(corridorLengthTemp <= corridorLength)
//							{
//								corridorLength = corridorLengthTemp;
//								splitFinal = splitPoint;
//							}
						}
					}					
				}
				if(distance1 == 5000 || distance2 == 5000)
				{
					corridor = new Rect(0,0,10,10);
				}
				else
				{
					corridor = new Rect(rooms[room1].x + rooms[room1].width,splitPoint - 2,distance1 + distance2,4);
				}
			}	
			leftChild.GenerateCorridors(rooms,roomTotal);
			rightChild.GenerateCorridors(rooms,roomTotal);
		}
	}
	
	public void TraverseCorridors(Rect[] corridors)
	{
		if(leftChild != null)
		{
			corridors[nodeIndex - 1] = corridor;
			leftChild.TraverseCorridors(corridors);
			rightChild.TraverseCorridors(corridors);
		}
	}
	
//	public float CheckCorridors(float x,float y,bool horizontal, bool first)
//	{		
//		if(leftChild != null)
//		{
//			float result1 = leftChild.CheckCorridors(x,y,horizontal,true);
//			float result2 = rightChild.CheckCorridors(x,y,horizontal,false);
//			if(result1 > 0)
//			{
//				return result1;
//			}
//			else
//			{
//				return result2;
//			}
//		}
//		else
//		{
//			if(horizontal == true)
//			{				
//				if(room.x < x && (room.x + room.width) > x)
//				{
//					if(first == true)
//					{
//						return room.y + room.height;
//					}
//					else
//					{
//						return room.y;
//					}
//				}
//				else
//				{
//					return -1;
//				}
//			}
//			else
//			{
//				if(room.y < y && (room.y + room.height) > y)
//				{
//					if(first == true)
//					{
//						return room.x + room.width;
//					}
//					else
//					{
//						return room.x;
//					}
//				}
//				else
//				{
//					return -1;
//				}	
//			}
//		}	
//	}
	
	public int CountNodes(int nodeTotal)
	{
		if(nodeIndex >= nodeTotal)
		{
			nodeTotal = nodeIndex;
		}
		if(leftChild != null)
		{
			nodeTotal = rightChild.CountNodes(nodeTotal);
		}
		return nodeTotal;
	}
	
	public int CountRooms(int nodeTotal)
	{		
		int leafIndex;
		leafIndex = GetLeafIndex(0);
		int roomTotal = (nodeTotal - leafIndex) + 1;
		return roomTotal;
	}
	
	public int GetLeafIndex(int leafIndex)
	{
		if(nodeIndex >= leafIndex)
		{
			leafIndex = nodeIndex;
		}
		if(leftChild != null)
		{
			leafIndex = leftChild.GetLeafIndex(leafIndex);
		}
		return leafIndex;
	}
}
